package com.leetcode.weekly.contest.no281th;

import java.io.FileInputStream;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * @author 覃国强
 * @date 2022-02-20 11:28
 */
public class A04_统计可以被K整除的下标对数目 {


  public static void main(String[] args) throws Exception {
    Solution solution = new Solution();

    Scanner scanner = new Scanner(new FileInputStream("/Users/stars/work/stars/leetcode/src/main/resources/array1"));


    String[] strs = scanner.nextLine().split(",");
    int[] nums = new int[strs.length];
    for (int i = 0; i < strs.length; ++i) {
      nums[i] = Integer.parseInt(strs[i]);
    }
    int k = 55503;

    long r1 = solution.countPairs(nums, k);
    long r2 = solution.coutPairs(nums, k);

    System.out.println("r1: " + r1);
    System.out.println("r2: " + r2);


  }

  static
  class Solution {

    public long countPairs(int[] nums, int k) {

      long result = 0;
      for (int i = 0; i < nums.length; ++i) {
        for (int j = i + 1; j < nums.length; ++j) {
          if ((nums[i] * nums[j]) % k == 0) {
            ++result;
          }
        }
      }

      return result;
    }

    public long coutPairs(int[] nums, int k) {

      long result = 0;
      Map<Integer, Integer> map = new HashMap<>();
      for (int num : nums) {
        if (!map.containsKey(num)) {
          map.put(num, 1);
        } else {
          map.put(num, map.get(num) + 1);
        }
      }

      for (int i = 0; i < nums.length; ++i) {
        if (nums[i] % k == 0) {
          result += (nums.length - i - 1);
          continue;
        }
        if (k % nums[i] == 0) {
          int temp = k / nums[i];
          if (map.containsKey(temp)) {
            result += map.get(temp);
          }
        }
      }

      return result;
    }
  }

}
